package org.raymond.iworks.study.basic.structure.tree.binarytree;

/**
 * @author raymond
 * @version V1.0
 * @Description:
 * 顺序存储二叉树
 * 基本说明
 * 从数据存储来看,数据存储方式和数的存储方式可以相互转换,即数组可以转换成树,树也可以转换成数组
 *         1(0)
 *    2(1)       3(2)
 * 4(3) 5(4)  6(5) 7(6)
 *
 * 要求:
 * 1) 上图的二叉树的节点,要求以数组的方式来存放arr[1,2,3,4,5,6,7],括号中的数字表示数组arr的下标
 * 2) 要求在遍历数组arr时,仍然可以以前序遍历,中序遍历和后序遍历的方式来完成节点的遍历
 *
 * 顺序存储二叉树的特点
 * 1) 顺序二叉树通常指考虑完全二叉树
 * 2) 第n个元素的左子节点为2*n+1,例如:arr[1],n=1,则其左子节点的下标为2*n+1=3
 * 3) 第n个元素的右子节点为2*n+2,例如:arr[1],n=1,则其右子节点的下标为2*n+2=4
 * 4) 第n个元素的父节点为(n-1)/2,例如:arr[1],n=1,则其父节点的下标为(n-1)/2=0
 * 5) n:表示二叉树中的第几个元素(按0开始编号)
 *
 * 应用实例:
 * 八大排序算法中的堆排序,就会使用到顺序存储二叉树
 *
 * 中序,后序?
 */
public class ArrBinaryTreeDemo {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7};
        ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
        arrBinaryTree.preOrder(); // 1,2,4,5,3,6,7, ok
        System.out.println("===========");
        arrBinaryTree.infixOrder(); // 4,2,5,1,6,3,7, ok
        System.out.println("===========");
        arrBinaryTree.postOrder(); // 4,5,2,6,7,3,1, ok
    }
}

// 编写一个ArrayBinaryTree,实现顺序存储二叉树遍历
class ArrBinaryTree {
    // 存储数据节点的数组
    private int[] arr;
    public ArrBinaryTree(int[] arr) {
        this.arr = arr;
    }
    public void preOrder(){
        preOrder(0);
    }
    public void infixOrder(){
        infixOrder(0);
    }
    public void postOrder(){
        postOrder(0);
    }
    /**
     * 编写一个方法,完成顺序存储二叉树的前序遍历
     * @param index 数组下标
     */
    public void preOrder(int index){
        // 如果数组为空,或者arr.length=0
        if(arr==null || arr.length==0){
            System.out.println("数组为空,不能按照二叉树的前序遍历");
            return;
        }
        // 输出当前元素
        System.out.println(arr[index]);
        // 向左递归遍历
        if((2*index+1)<arr.length) {
            preOrder(2*index+1);
        }
        // 向右递归遍历
        if((2*index+2)<arr.length) {
            preOrder(2*index+2);
        }
    }

    public void infixOrder(int index){
        // 如果数组为空,或者arr.length=0
        if(arr==null || arr.length==0){
            System.out.println("数组为空,不能按照二叉树的中序遍历");
            return;
        }
        // 向左递归遍历
        if((2*index+1)<arr.length) {
            infixOrder(2*index+1);
        }
        // 输出当前元素
        System.out.println(arr[index]);
        // 向右递归遍历
        if((2*index+2)<arr.length) {
            infixOrder(2*index+2);
        }
    }
    public void postOrder(int index){
        // 如果数组为空,或者arr.length=0
        if(arr==null || arr.length==0){
            System.out.println("数组为空,不能按照二叉树的后序遍历");
            return;
        }
        // 向左递归遍历
        if((2*index+1)<arr.length) {
            postOrder(2*index+1);
        }
        // 向右递归遍历
        if((2*index+2)<arr.length) {
            postOrder(2*index+2);
        }
        // 输出当前元素
        System.out.println(arr[index]);
    }
}

